- Title
- On the nonexistence of graphs of diameter 2 and defect 2
- Creator
- Miller, Mirka; Nguyen, Minh Hoang; Pineda-Villavicencio, Guillermo
- Relation
- Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, p. 5-20
- Relation
- http://www.charlesbabbage.org
- Publisher
- Charles Babbage Research Centre
- Resource Type
- journal article
- Date
- 2009
- Description
- In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2,3,7 and possibly 57. In 1980, Erdős et al., using eigenvalue analysis, showed that, with the exception of C₄ , there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.
- Subject
- graph theory; vertices; eigenvalue; diameter
- Identifier
- http://hdl.handle.net/1959.13/916879
- Identifier
- uon:8137
- Identifier
- ISSN:0835-3026
- Language
- eng
- Reviewed
- Hits: 1307
- Visitors: 1469
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|